package com.example.arithmeticleetcode.learnArithmetic2.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @program: arithmetic-leetcode
 * @description: 最好 最坏 平均 时间复杂度O(d*(n + k)) d为最大值的位数 空间复杂度  稳定排序
 * @author: FangZhen
 * @create: 2020-11-11 16:34
 **/
public class RedixSort extends Sort<Integer> { //和计数排序一样都是针对整数的


    @Override
    protected void sort() {
        //找出最大值
        int max = array[0];
        for (int i = 0, len = array.length; i < len; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }

        for (int divider = 1; divider < max; divider *= 10) {
            countingSort(divider);
        }

    }

    public static void main(String[] args) {
        List<Integer>[] lists = new List[2];
        for (int i = 0; i < lists.length; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1 + i);
            list.add(2 + i);
            lists[i] = list;
        }
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    protected void countingSort(int divider) {

        //求出最大值，最小值
        int max = array[0], min = array[0];
        for (int i = 1, len = array.length; i < len; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        //开辟内存空间，统计每个整数出现的次数
        int[] counts = new int[10];

        //统计每个整数出现的次数
        for (int i = 0, len = array.length; i < len; i++) {
            counts[array[i] / divider % 10]++;
        }

        //累加次数
        for (int i = 1, len = counts.length; i < len; i++) {
            counts[i] += counts[i - 1];
        }

        //从后往前遍历元素，将他放到有序元素的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {

            newArray[--counts[array[i] / divider % 10]] = array[i];
        }

        //将有序数组赋值到array
        for (int i = 0, len = newArray.length; i < len; i++) {
            array[i] = newArray[i];
        }
    }
}
